package leetcode.code1703;

import java.util.ArrayList;
import java.util.List;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;

public class Solution3 implements IDebug {

	public int minMoves(int[] nums, int k) {
		if (k == 1) {
			return 0;
		}
		int len = nums.length;
		List<Integer> g = new ArrayList<>(len);
		for (int i = 0; i < len; i++) {
			if (nums[i] == 1) {
				g.add(i - g.size());
			}
		}
		int gSize = g.size();
		int[] sums = new int[gSize + 1];
		for (int i = 1; i <= gSize; i++) {
			sums[i] = sums[i - 1] + g.get(i - 1);
		}
		int ans = Integer.MAX_VALUE;
		for (int i = 0; i + k <= gSize; ++i) {
			int mid = (i + i + k - 1) / 2;
			int q = g.get(mid);
			ans = Math.min(ans, (2 * (mid - i) - k + 1) * q + (sums[i + k] - sums[mid + 1]) - (sums[mid] - sums[i]));
		}
		return ans;
	}

	@Override
	public void debug1() {
		HelpDebug.compare(6, this.minMoves(HelpDebug.str2array3("[1,0,0,1,1,0,0,0,0,1]"), 4));

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub
		HelpDebug.compare(8, this.minMoves(HelpDebug.str2array3("[1,1,0,0,1,0,0,0,0,1]"), 4));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

		HelpDebug.compare(8, this.minMoves(HelpDebug.str2array3("[1,1,0,0,1,0,1,0,0,1]"), 5));
	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub
		HelpDebug.compare(10, this.minMoves(HelpDebug.str2array3("[1,1,0,0,0,0,0,1,1,1]"), 5));

	}

	public void debug5() {
		// TODO Auto-generated method stub
		HelpDebug.compare(8, this.minMoves(HelpDebug.str2array3("[1,0,0,1,0,0,1,0,1,1]"), 5));

	}

	public void debug6() {
		// TODO Auto-generated method stub
		HelpDebug.compare(0, this.minMoves(HelpDebug.str2array3("[1,1]"), 1));

	}

	public void debug7() {
		// TODO Auto-generated method stub
		HelpDebug.compare(1, this.minMoves(HelpDebug.str2array3("[1,0,1,1,1,1,1,1,1,1,1,1,1,1,1]"), 14));

	}

	public void debug8() {
		// TODO Auto-generated method stub
		HelpDebug.compare(4, this.minMoves(HelpDebug.str2array3("[0,1,0,0,1,1,0,1,0,1,1,1,1,0,1,0]"), 7));

	}

	public static void main(String[] args) {
		Solution3 so = new Solution3();
		so.debug8();
		so.debug7();
		so.debug6();
		so.debug5();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
